/* 368. 最大整除子集 */
/**
 * @param {number[]} nums
 * @return {number[]}
 */
/* 
    整除关系具有传递性即 a|b 并且 b|c 那么 a|c
*/
var largestDivisibleSubset = function (nums) {
    nums.sort((a, b) => a - b)
    const len = nums.length
    /* 
        dp[i]:表示当前 num 的最大整除子集
    */
    const dp = new Array(len).fill(0).map((_, index) => [nums[index]])
    let maxIndex = 0, maxLen = 0
    for (let i = 1; i < len; i++) {
        for (let j = i - 1; j >= 0; j--) {
            if (nums[i] % nums[j] === 0) {
                const temp = [...dp[j], nums[i]]
                dp[i] = dp[i].length < temp.length ? temp : dp[i]
                maxLen = Math.max(maxLen, dp[i].length)
                if (maxLen === dp[i].length) {
                    maxIndex = i
                }
            }
        }
    }
    return dp[maxIndex]
};
const result = largestDivisibleSubset([2, 3, 4, 9, 8])
console.log('largestDivisibleSubset :>>', result);